package com.graph;

import lombok.Data;
import lombok.Getter;
import lombok.Setter;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-10-22 09:43
 */
public interface Graph<V,E> {

     abstract class Traversal<V>{

        boolean stop;
        abstract boolean visitor(V v);
    }

    @Data
    class EdgeInfo<V,E> {

         private V from;
         private V to;
         private E weight;

        public EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }


    @Setter
    @Getter
    class ShortestPath<V,E>{

         List<V> paths;
         E pathLength;

        public ShortestPath() {

            paths = new ArrayList<>();
        }

        @Override
        public String toString() {

            return  pathLength +  " paths:" + paths;
        }
    }

    @Setter
    @Getter
    class PathInfos<V,E> {

         private List<EdgeInfo<V,E>> paths;
         private E weight;

        public PathInfos() {

            this(null);
        }

        public PathInfos(E weight) {
            this.weight = weight;
            paths = new LinkedList<>();
        }

        @Override
        public String toString() {
            return "weight:" + weight +  " paths:" + paths.toString();
        }
    }

    /**
     * 图的节点数
     * @return
     */
    int verticesSize();

    /**
     * 边的条数
     * @return
     */
    int edgesSize();

    /**
     * 添加节点
     * @param v
     */
    void addVertex(V v);

    /**
     * 删除节点
     * @param v
     */
    void removeVertex(V v);

    /**
     * 添加节点
     * @param from 起始节点
     * @param to 结束节点
     */
    void addEdge(V from, V to);

    /**
     * 广度优先搜索
     * breadth first search
     *
     * @param traversal
     */
    void bfs(V v,Traversal<V> traversal);

    /**
     * 深度优先搜索
     * depth first search
     * @param traversal
     */
    void dfs(V v,Traversal<V> traversal);


    /**
     * 添加节点和权值
     * @param from 起始节点
     * @param to 结束节点
     * @param weight 边的权值
     */
    void addEdge(V from, V to ,E weight);

    /**
     * 删除边
     * @param from 起始节点
     * @param to 结束节点
     */
    void removeEdge(V from, V to);

    List<V> topologicalsort();

    /**
     * 最小生成树
     * @return
     */
    Set<EdgeInfo<V,E>> minimumSpanningTree();


    /**
     * 获取从v到其他节点到最小路径长度
     * @param v 起点节点v
     * @return
     */
    Map<V,ShortestPath<V,E>> customShortestPath(V v);

    Map<V,PathInfos<V,E>> shortestPath(V v);

    Map<V,Map<V,PathInfos<V,E>>> allShortestPath();
}
